home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / PCTAGS15.ARJ / FILMATCH.C < prev    next >
C/C++ Source or Header  |  1991-09-25  |  16KB  |  494 lines
  1. /*
  2.  EPSHeader
  3.  
  4.    File: filmatch.c
  5.    Author: J. Kercheval
  6.    Created: Thu, 03/14/1991  22:22:01
  7. */
  8.  
  9. /*
  10.  EPSRevision History
  11.  
  12.    J. Kercheval  Wed, 02/20/1991  22:29:01  Released to Public Domain
  13.    J. Kercheval  Fri, 02/22/1991  15:29:01  fix '\' bugs (two :( of them)
  14.    J. Kercheval  Sun, 03/10/1991  19:31:29  add error return to matche()
  15.    J. Kercheval  Sun, 03/10/1991  20:11:11  add is_valid_pattern code
  16.    J. Kercheval  Sun, 03/10/1991  20:37:11  beef up main()
  17.    J. Kercheval  Tue, 03/12/1991  22:25:10  Released as V1.1 to Public Domain
  18.    J. Kercheval  Thu, 03/14/1991  22:22:25  remove '\' for DOS file parsing
  19.    J. Kercheval  Thu, 03/28/1991  20:58:27  include filmatch.h
  20. */
  21.  
  22. /*
  23.    Wildcard Pattern Matching
  24. */
  25.  
  26.  
  27. #include "filmatch.h"
  28.  
  29. int matche_after_star(register char *pattern, register char *text);
  30. int fast_match_after_star(register char *pattern, register char *text);
  31.  
  32. /*----------------------------------------------------------------------------
  33. *
  34. * Return TRUE if PATTERN has any special wildcard characters
  35. *
  36. ----------------------------------------------------------------------------*/
  37.  
  38. BOOLEAN is_pattern(char *p)
  39. {
  40.     while (*p) {
  41.         switch (*p++) {
  42.                 case '?':
  43.                 case '*':
  44.                 case '[':
  45.                 return TRUE;
  46.         }
  47.     }
  48.     return FALSE;
  49. }
  50.  
  51.  
  52. /*----------------------------------------------------------------------------
  53. *
  54. * Return TRUE if PATTERN has is a well formed regular expression according
  55. * to the above syntax
  56. *
  57. * error_type is a return code based on the type of pattern error.  Zero is
  58. * returned in error_type if the pattern is a valid one.  error_type return
  59. * values are as follows:
  60. *
  61. *   PATTERN_VALID - pattern is well formed
  62. *   PATTERN_RANGE - [..] construct has a no end range in a '-' pair (ie [a-])
  63. *   PATTERN_CLOSE - [..] construct has no end bracket (ie [abc-g )
  64. *   PATTERN_EMPTY - [..] construct is empty (ie [])
  65. *
  66. ----------------------------------------------------------------------------*/
  67.  
  68. BOOLEAN is_valid_pattern(char *p, int *error_type)
  69. {
  70.  
  71.     /* init error_type */
  72.     *error_type = PATTERN_VALID;
  73.  
  74.     /* loop through pattern to EOS */
  75.     while (*p) {
  76.  
  77.         /* determine pattern type */
  78.         switch (*p) {
  79.  
  80.                 /* the [..] construct must be well formed */
  81.             case '[':
  82.                 p++;
  83.  
  84.                 /* if the next character is ']' then bad pattern */
  85.                 if (*p == ']') {
  86.                     *error_type = PATTERN_EMPTY;
  87.                     return FALSE;
  88.                 }
  89.  
  90.                 /* if end of pattern here then bad pattern */
  91.                 if (!*p) {
  92.                     *error_type = PATTERN_CLOSE;
  93.                     return FALSE;
  94.                 }
  95.  
  96.                 /* loop to end of [..] construct */
  97.                 while (*p != ']') {
  98.  
  99.                     /* check for literal escape */
  100.                     if (*p == '\\') {
  101.                         p++;
  102.  
  103.                         /* if end of pattern here then bad pattern */
  104.                         if (!*p++) {
  105.                             *error_type = PATTERN_ESC;
  106.                             return FALSE;
  107.                         }
  108.                     }
  109.                     else
  110.                         p++;
  111.  
  112.                     /* if end of pattern here then bad pattern */
  113.                     if (!*p) {
  114.                         *error_type = PATTERN_CLOSE;
  115.                         return FALSE;
  116.                     }
  117.  
  118.                     /* if this a range */
  119.                     if (*p == '-') {
  120.  
  121.                         /* we must have an end of range */
  122.                         if (!*++p || *p == ']') {
  123.                             *error_type = PATTERN_RANGE;
  124.                             return FALSE;
  125.                         }
  126.                         else {
  127.  
  128.                             /* check for literal escape */
  129.                             if (*p == '\\')
  130.                                 p++;
  131.  
  132.                             /* if end of pattern here then bad pattern */
  133.                             if (!*p++) {
  134.                                 *error_type = PATTERN_ESC;
  135.                                 return FALSE;
  136.                             }
  137.                         }
  138.                     }
  139.                 }
  140.                 break;
  141.  
  142.                 /* all other characters are valid pattern elements */
  143.             case '*':
  144.             case '?':
  145.             default:
  146.                 p++;            /* "normal" character */
  147.                 break;
  148.         }
  149.     }
  150.  
  151.     return TRUE;
  152. }
  153.  
  154.  
  155. /*----------------------------------------------------------------------------
  156. *
  157. *  Match the pattern PATTERN against the string TEXT;
  158. *
  159. *  returns MATCH_VALID if pattern matches, or an errorcode as follows
  160. *  otherwise:
  161. *
  162. *            MATCH_PATTERN  - bad pattern
  163. *            MATCH_RANGE    - match failure on [..] construct
  164. *            MATCH_ABORT    - premature end of text string
  165. *            MATCH_END      - premature end of pattern string
  166. *            MATCH_VALID    - valid match
  167. *
  168. *
  169. *  A match means the entire string TEXT is used up in matching.
  170. *
  171. *  In the pattern string:
  172. *       `*' matches any sequence of characters (zero or more)
  173. *       `?' matches any character
  174. *       [SET] matches any character in the specified set,
  175. *       [!SET] or [^SET] matches any character not in the specified set.
  176. *       \ is allowed within a set to escape a character like ']' or '-'
  177. *
  178. *  A set is composed of characters or ranges; a range looks like
  179. *  character hyphen character (as in 0-9 or A-Z).  [0-9a-zA-Z_] is the
  180. *  minimal set of characters allowed in the [..] pattern construct.
  181. *  Other characters are allowed (ie. 8 bit characters) if your system
  182. *  will support them.
  183. *
  184. *  To suppress the special syntactic significance of any of `[]*?!^-\',
  185. *  within a [..] construct and match the character exactly, precede it
  186. *  with a `\'.
  187. *
  188. ----------------------------------------------------------------------------*/
  189.  
  190. int matche(register char *p, register char *t)
  191. {
  192.     register char range_start, range_end;       /* start and end in range */
  193.  
  194.     BOOLEAN invert;             /* is this [..] or [!..] */
  195.     BOOLEAN member_match;       /* have I matched the [..] construct? */
  196.     BOOLEAN loop;               /* should I terminate? */
  197.  
  198.     for (; *p; p++, t++) {
  199.  
  200.         /* if this is the end of the text then this is the end of the match */
  201.         if (!*t) {
  202.             return (*p == '*' && *++p == '\0') ? MATCH_VALID : MATCH_ABORT;
  203.         }
  204.  
  205.         /* determine and react to pattern type */
  206.         switch (*p) {
  207.  
  208.                 /* single any character match */
  209.             case '?':
  210.                 break;
  211.  
  212.                 /* multiple any character match */
  213.             case '*':
  214.                 return matche_after_star(p, t);
  215.  
  216.                 /* [..] construct, single member/exclusion character match */
  217.             case '[':{
  218.  
  219.                     /* move to beginning of range */
  220.                     p++;
  221.  
  222.                     /* check if this is a member match or exclusion match */
  223.                     invert = FALSE;
  224.                     if (*p == '!' || *p == '^') {
  225.                         invert = TRUE;
  226.                         p++;
  227.                     }
  228.  
  229.                     /* if closing bracket here or at range start then we have
  230.                      * a malformed pattern */
  231.                     if (*p == ']') {
  232.                         return MATCH_PATTERN;
  233.                     }
  234.  
  235.                     member_match = FALSE;
  236.                     loop = TRUE;
  237.  
  238.                     while (loop) {
  239.  
  240.                         /* if end of construct then loop is done */
  241.                         if (*p == ']') {
  242.                             loop = FALSE;
  243.                             continue;
  244.                         }
  245.  
  246.                         /* matching a '!', '^', '-', '\' or a ']' */
  247.                         if (*p == '\\') {
  248.                             range_start = range_end = *++p;
  249.                         }
  250.                         else {
  251.                             range_start = range_end = *p;
  252.                         }
  253.  
  254.                         /* if end of pattern then bad pattern (Missing ']') */
  255.                         if (!*p)
  256.                             return MATCH_PATTERN;
  257.  
  258.                         /* check for range bar */
  259.                         if (*++p == '-') {
  260.  
  261.                             /* get the range end */
  262.                             range_end = *++p;
  263.  
  264.                             /* if end of pattern or construct then bad
  265.                              * pattern */
  266.                             if (range_end == '\0' || range_end == ']')
  267.                                 return MATCH_PATTERN;
  268.  
  269.                             /* special character range end */
  270.                             if (range_end == '\\') {
  271.                                 range_end = *++p;
  272.  
  273.                                 /* if end of text then we have a bad pattern */
  274.                                 if (!range_end)
  275.                                     return MATCH_PATTERN;
  276.                             }
  277.  
  278.                             /* move just beyond this range */
  279.                             p++;
  280.                         }
  281.  
  282.                         /* if the text character is in range then match
  283.                          * found. make sure the range letters have the proper
  284.                          * relationship to one another before comparison */
  285.                         if (range_start < range_end) {
  286.                             if (*t >= range_start && *t <= range_end) {
  287.                                 member_match = TRUE;
  288.                                 loop = FALSE;
  289.                             }
  290.                         }
  291.                         else {
  292.                             if (*t >= range_end && *t <= range_start) {
  293.                                 member_match = TRUE;
  294.                                 loop = FALSE;
  295.                             }
  296.                         }
  297.                     }
  298.  
  299.                     /* if there was a match in an exclusion set then no match */
  300.                     /* if there was no match in a member set then no match */
  301.                     if ((invert && member_match) ||
  302.                         !(invert || member_match))
  303.                         return MATCH_RANGE;
  304.  
  305.                     /* if this is not an exclusion then skip the rest of the
  306.                      * [...] construct that already matched. */
  307.                     if (member_match) {
  308.                         while (*p != ']') {
  309.  
  310.                             /* bad pattern (Missing ']') */
  311.                             if (!*p)
  312.                                 return MATCH_PATTERN;
  313.  
  314.                             /* skip exact match */
  315.                             if (*p == '\\') {
  316.                                 p++;
  317.  
  318.                                 /* if end of text then we have a bad pattern */
  319.                                 if (!*p)
  320.                                     return MATCH_PATTERN;
  321.                             }
  322.  
  323.                             /* move to next pattern char */
  324.                             p++;
  325.                         }
  326.                     }
  327.  
  328.                     break;
  329.                 }
  330.  
  331.                 /* must match this character exactly */
  332.             default:
  333.                 if (*p != *t)
  334.                     return MATCH_LITERAL;
  335.         }
  336.     }
  337.  
  338.     /* if end of text not reached then the pattern fails */
  339.     if (*t)
  340.         return MATCH_END;
  341.     else
  342.         return MATCH_VALID;
  343. }
  344.  
  345.  
  346. /*----------------------------------------------------------------------------
  347. *
  348. * recursively call matche() with final segment of PATTERN and of TEXT.
  349. *
  350. ----------------------------------------------------------------------------*/
  351.  
  352. int matche_after_star(register char *p, register char *t)
  353. {
  354.     register int match = 0;
  355.     register nextp;
  356.  
  357.     /* pass over existing ? and * in pattern */
  358.     while (*p == '?' || *p == '*') {
  359.  
  360.         /* take one char for each ? and + */
  361.         if (*p == '?') {
  362.  
  363.             /* if end of text then no match */
  364.             if (!*t++) {
  365.                 return MATCH_ABORT;
  366.             }
  367.         }
  368.  
  369.         /* move to next char in pattern */
  370.         p++;
  371.     }
  372.  
  373.     /* if end of pattern we have matched regardless of text left */
  374.     if (!*p) {
  375.         return MATCH_VALID;
  376.     }
  377.  
  378.     /* get the next character to match which must be a literal or '[' */
  379.     nextp = *p;
  380.  
  381.     /* Continue until we run out of text or definite result seen */
  382.     do {
  383.  
  384.         /* a precondition for matching is that the next character in the
  385.          * pattern match the next character in the text or that the next
  386.          * pattern char is the beginning of a range.  Increment text pointer
  387.          * as we go here */
  388.         if (nextp == *t || nextp == '[') {
  389.             match = matche(p, t);
  390.         }
  391.  
  392.         /* if the end of text is reached then no match */
  393.         if (!*t++)
  394.             match = MATCH_ABORT;
  395.  
  396.     } while (match != MATCH_VALID &&
  397.              match != MATCH_ABORT &&
  398.              match != MATCH_PATTERN);
  399.  
  400.     /* return result */
  401.     return match;
  402. }
  403.  
  404.  
  405. /*----------------------------------------------------------------------------
  406. *
  407. * match() is a shell to matche() to return only BOOLEAN values.
  408. *
  409. ----------------------------------------------------------------------------*/
  410.  
  411. BOOLEAN match(char *p, char *t)
  412. {
  413.     int error_type;
  414.  
  415.     error_type = matche(p, t);
  416.     return (error_type == MATCH_VALID) ? TRUE : FALSE;
  417. }
  418.  
  419.  
  420. #ifdef TEST
  421.  
  422.  /* This test main expects as first arg the pattern and as second arg the
  423.   * match string.  Output is yaeh or nay on match.  If nay on match then the
  424.   * error code is parsed and written. */
  425.  
  426. #include <stdio.h>
  427.  
  428. int main(int argc, char *argv[])
  429. {
  430.     int error;
  431.     int is_valid_error;
  432.  
  433.     if (argc != 3) {
  434.         printf("Usage:  MATCH Pattern Text\n");
  435.     }
  436.     else {
  437.         printf("Pattern: %s\n", argv[1]);
  438.         printf("Text   : %s\n", argv[2]);
  439.  
  440.         if (!is_pattern(argv[1])) {
  441.             printf("    First Argument Is Not A Pattern\n");
  442.         }
  443.         else {
  444.             match(argv[1], argv[2]) ? printf("TRUE") : printf("FALSE");
  445.             error = matche(argv[1], argv[2]);
  446.             is_valid_pattern(argv[1], &is_valid_error);
  447.  
  448.             switch (error) {
  449.                 case MATCH_VALID:
  450.                     printf("    Match Successful");
  451.                     if (is_valid_error != PATTERN_VALID)
  452.                         printf(" -- is_valid_pattern() is complaining\n");
  453.                     else
  454.                         printf("\n");
  455.                     break;
  456.                 case MATCH_RANGE:
  457.                     printf("    Match Failed on [..]\n");
  458.                     break;
  459.                 case MATCH_ABORT:
  460.                     printf("    Match Failed on Early Text Termination\n");
  461.                     break;
  462.                 case MATCH_END:
  463.                     printf("    Match Failed on Early Pattern Termination\n");
  464.                     break;
  465.                 case MATCH_PATTERN:
  466.                     switch (is_valid_error) {
  467.                         case PATTERN_VALID:
  468.                             printf("    Internal Disagreement On Pattern\n");
  469.                             break;
  470.                         case PATTERN_RANGE:
  471.                             printf("    No End of Range in [..] Construct\n");
  472.                             break;
  473.                         case PATTERN_CLOSE:
  474.                             printf("    [..] Construct is Open\n");
  475.                             break;
  476.                         case PATTERN_EMPTY:
  477.                             printf("    [..] Construct is Empty\n");
  478.                             break;
  479.                         default:
  480.                             printf("    Internal Error in is_valid_pattern()\n");
  481.                     }
  482.                     break;
  483.                 default:
  484.                     printf("    Internal Error in matche()\n");
  485.                     break;
  486.             }
  487.         }
  488.  
  489.     }
  490.     return (0);
  491. }
  492.  
  493. #endif
  494.